C# 程式基礎

常見演算法：

• 分治法（Divide and Conquer）
• 遞迴（Recursion）

分治法（Divide and Conquer）：

• 基本概念：
  • 基本思想是將問題分解成可解決的子問題，這些子問題的結果結合起來就是原始問題的解決方案。
  • 通常，這種方法在每一個階段都採用相同的演算法來處理子問題。
• 步驟：
  1. 分割（Divide）：將原始問題分成幾個較小的子問題，這些子問題通常是相互獨立的。
  2. 解決（Conquer）：解決每個子問題，通常採用遞迴或其他方法。
  3. 合併（Combine）：將子問題的解合成原始問題的解。
• 程式實作（計算array總和）：

  // 分冶法計算陣列總和
  public static int Sum(int[] arr)
  {
      // 基本情況：如果陣列只有一個元素，直接返回該元素的值
      if (arr.Length == 1)
          return arr[0];
  
      // 否則，將陣列分為兩半
      int mid = arr.Length / 2;
      int[] leftHalf = new int[mid];
      int[] rightHalf = new int[arr.Length - mid];
  
      // 將元素分到左右兩半
      for (int i = 0; i < mid; i++)
          leftHalf[i] = arr[i];
      for (int i = mid; i < arr.Length; i++)
          rightHalf[i - mid] = arr[i];
  
      // 遞迴計算左右兩半的總和，然後合併
      int leftSum = Sum(leftHalf);
      int rightSum = Sum(rightHalf);
  
      return leftSum + rightSum;
  }
  
  static void Main(string[] args)
  {
      int[] arr = { 1, 2, 3, 4, 5 };
      int sum = Sum(arr);
      Console.WriteLine("陣列總和：" + sum);
  }
  
  

遞迴（Recursion）：

• 基本概念：
  • 基本思想是將一個大問題分解成較小的子問題，然後遞迴地處理這些子問題，直到達到停止條件，然後將它們的結果合併為原始問題的解。
• 基本結構：
  1. 遞迴函數（Recursive Function）：
     一個能夠呼叫自己的函數。在每一個遞迴步驟中，它會處理子問題。
  2. 基本情況（Base Case）：
     遞迴函數中的一個條件，用於確定何時停止遞迴。當遞迴函數到達基本情況時，它將不再呼叫自己，而是返回一個結果。
  3. 遞迴關係（Recursive Relation）：
     定義如何將原始問題分解成子問題，以及如何將子問題的結果合併為原始問題的解。
• 程式實作(計算階層)：

  static int Factorial(int n)
  {
      // 基本情況：階層的基本情況是 0! = 1
      if (n == 0)
          return 1;
  
      // 遞迴關係：n! = n * (n-1)!
      return n * Factorial(n - 1);
  }
  
  static void Main(string[] args)
  {
      int n = 5;
      int result = Factorial(n);
      Console.WriteLine($"{n} 的階層是 {result}");
  }
  

程式實作練習：

• 分治法（Divide and Conquer）：
  • leetcode-53. Maximum Subarray
• 遞迴（Recursion）：
  • leetcode-231. Power of Two

參考來源

1. ChatGPT
2. C#最強入門邁向頂尖高手之路王者歸來
3. w3schools C#
4. 圖解資料結構 × 演算法:運用C#
5. Leetcode - Divide and Conquer

期望挑戰30天持續更新成功 ～ DAY21